#define _CRT_SECURE_NO_WARNINGS

#include "heapsort.h"
void heapsort(int* nums, int numsSize)
{
	if (nums == NULL || numsSize < 2)
		return;
	for (int i = 0; i < numsSize; ++i)
	{
		heapIndex(nums, i);
	}
	swap(nums, 0, --numsSize);
	while (numsSize > 0)
	{
		heapify(nums, 0, numsSize);
		swap(nums, 0, --numsSize);
	}
}

void heapIndex(int* nums, int index)
{
	while (nums[index] > nums[(index - 1) / 2])
	{
		swap(nums, index, (index - 1) / 2);
		index = (index - 1) / 2;
	}
}

void heapify(int* nums, int index, int numsSize)
{
	int left = index * 2 + 1;
	while (left < numsSize)
	{
		int large = left + 1 < numsSize && nums[left + 1] > nums[left] ? left + 1 : left;
		large = nums[large] > nums[index] ? large : index;
		if (large == index)
			break;
		swap(nums, index, large);
		index = large;
		left = index * 2 + 1;
	}
}

void swap(int* nums, int a, int b)
{
	int temp = nums[a];
	nums[a] = nums[b];
	nums[b] = temp;
}